package dataStructLinkedList;

import java.util.LinkedList;
import java.util.List;

public class testLeeCoNiuKe {
    public static void main(String[] args) {

    }

    public ListNode detectCycle(ListNode head) {

        if(head == null || head.next == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }

        if(fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;

        while (cur != null){
            if( cur.val == val ){
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }

        }
        if (head.val == val){
            head = head.next;
        }
        return head;
    }


    //头插法




//
//    public boolean hasCycle(ListNode head) {
//
//        ListNode fast = head;
//        ListNode slow = head;
//        if(head == null || head.next == null){
//            return false;
//        }
//        while (fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow){
//                return true;
//            }
//        }
//        return false;
//
//
//    }



//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//
//        int lenA = 0;
//        int lenB = 0;
//        int len = 0;
//        //  假设A链表 更长
//        ListNode longList = headA;
//        ListNode shotList = headB;
//
//        while (longList != null){
//            longList = longList.next;
//            lenA++;
//        }
//        while (shotList != null){
//            shotList = shotList.next;
//            lenB++;
//        }
//        longList = headA;
//        shotList = headB;
//        //  假设A链表 更长
//        len = lenA - lenB;
//        //  不是再变为 B
//        if(len < 0){
//            len = lenB - lenA;
//            longList = headB;
//            shotList = headA;
//        }
//        while (len != 0){
//            longList = longList.next;
//            len--;
//        }
//        while (longList != shotList){
//            longList = longList.next;
//            shotList = shotList.next;
//        }
//        if(longList == null || shotList == null){
//            return null;
//        }
//        return longList;

//    }
//



//    public ListNode partition(ListNode pHead, int x) {

        // write code here



//    public ListNode removeElements(ListNode head, int val) {
//
//        if(head == null){
//            return null;
//        }
//        ListNode pre = head;
//        ListNode cur = head.next;
//        while (cur != null){
//            if (cur.val == val){
//                pre.next = cur.next;
//                cur = cur.next;
//            }else{
//                pre = cur;
//                cur = cur.next;
//            }
//        }
//        if(head.val == val){
//            head = head.next;
//        }
//        return head;
//    }

//    public ListNode reverseList(ListNode head){
//        if(head == null){
//            return null;
//        }
//        if (head.next == null){
//            return head;
//        }
//        //  反转链表，可以用头插法
//        ListNode tou = head;
//        ListNode wei = head.next;
//        while (wei != null){
//            tou.next = wei.next;
//            wei.next = head;
//            head = wei;
//            wei = tou.next;
//        }
//        return head;
//    }



//    public ListNode middleNode(ListNode head){
//
//        ListNode fast = head;
//        ListNode slow = head;
//
//        while (fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        return slow;
//
//    }

//    public ListNode FindKthToTail(ListNode head,int k){
//
//        //  判断 k 是否符合范围
//        if(k <= 0 || head == null){
//            return null;
//        }
//
//        //  快慢指针
//        ListNode fast = head;
//        ListNode slow = head;
//        //  倒数第K个
//        //  则fast先走k-1步，然后再快慢指针一起走，直到终点。
//        //  此时的slow指针 就是所求的倒数第K个结点
//        while (k-1 != 0){
//            fast = fast.next;
//            if(fast == null){
//                return null;
//            }
//            k--;
//        }
//
//        while (fast !=null && fast.next != null){
//            fast = fast.next;
//            slow = slow.next;
//        }
//        return slow;
//
//    }

//    public boolean chkPalindrome(ListNode A) {
//
//        // write code here
//        if(A == null){
//            return false;
//        }
//        if(A.next == null){
//            return true;
//        }
//        ListNode fast = A;
//        ListNode slow = A;
//        //  第一步 找出中间节点
//        while (fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //  第二步 翻转
//        ListNode cur = slow.next;
//        while (cur != null){
//            ListNode curNext = cur.next;
//            cur.next = slow;
//            slow = cur;
//            cur = curNext;
//        }
//        //  第三步 比较大小是否相等
//        while (A != slow){
//            if(A.val != slow.val){
//                return false;
//            }
//            if(A.next == slow){
//                return true;
//            }
//            A = A.next;
//            slow = slow.next;
//        }
//        return true;
//
//
//    }

//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//
//
//        ListNode head1 = list1;
//        ListNode head2 = list2;
//
//        if(head1 == null){
//            return head2;
//        }
//        if(head2 == null){
//            return head1;
//        }
//
//        ListNode cur = new ListNode();
//        ListNode newHead = cur;
//        while (head1 != null && head2 != null){
//            if(head1.val <= head2.val){
//                cur.next= head1;
//                head1 = head1.next;
//                cur = cur.next;
//            }else {
//                cur.next = head2;
//                head2 = head2.next;
//                cur = cur.next;
//            }
//        }
//        if(head1 == null){
//            cur.next = head2;
//        }
//        if(head2 == null){
//            cur.next = head1;
//        }
//        return newHead.next;
//
//    }

//    public ListNode FindKthToTail(ListNode head,int k) {
//
//
////        ListNode fast = head;
////        ListNode slow = head;
////
////        for (int i = 0; i < k-1; i++) {
////            fast = fast.next;
////        }
////        while (fast != null && fast.next != null){
////            fast = fast.next;
////            slow = slow.next;
////        }
////        return slow;
//    }

}
